package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 187. 重复的DNA序列
 * @date 2025/9/30 11:17
 */
public class E187 {

    /**
     * 思路：滑动窗口配合哈希表
     *
     * @param s DNA序列
     * @return 重复的DNA序列
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() <= 10) return result;
        Map<String, Integer> map = new HashMap<String, Integer>();
        char[] charArray = s.toCharArray();
        int start = 0;
        for (int end = 9; end < charArray.length; end++, start++) {
            String key = new String(charArray, start, end - start + 1);
            map.compute(key, (k, v) -> v == null ? 1 : v + 1);
        }
        map.forEach((k, v) -> {
            if (map.get(k) > 1) result.add(k);
        });
        return result;
    }
}
